In data unit based communication, i.e. in which an information to be transmitted is divided into a plurality of units, and the individual units are sent over a communication network, its is known to provide queue buffers at links along the network, such that units transported over such a link may be buffered. The buffer may be a sending or input buffer (i.e. a buffer for data units that are to be sent over the link) or a receiving or output buffer (i.e. a buffer for data units that have been sent over the link).
Such units for transporting data may carry a variety of names, such as protocol data units, frames, packets, segments, cells, etc., depending on the specific context, the specific protocol used and certain other conventions. In the context of the present document, all such units of data shall generically be referred to as data units.
The procedures for placing data units into a queue, advancing them in the queue, and removing data units from the queue are referred to as queue management.
A phenomenon that is known in data unit transmission networks is that of so-called congestion. Congestion implies a state in which it is not possible to readily handle the number of data units, that are to be transported over that connection or link. As a consequence of congestion at a given link, the number of data units in a queue buffer associated with said link will increase. In response to a congestion condition, it is known to implement a data unit dropping mechanism referred to as drop-on-full, according to which upon the receipt a new data unit for the queue buffer, a queue length related parameter, such as the actual queue length or the average queue length, is compared to a predetermined threshold, and if the predetermined threshold is exceeded, then a data unit is dropped. The threshold indicates the full state of the queue. “Dropping” means that it is not placed into the queue and consequently not transported further.
The data unit to be dropped can be the newly arrived one, in which case the mechanism is called tail-drop. Besides the technique of tail-drop, it is also known to perform a so-called random-drop, where a data unit already in the queue is selected according to a random function, or a so-called front-drop, where the first data unit in the queue is dropped. Such drop-on-full mechanisms not only serve to reduce the load on the congested link, but also serve as an implicit congestion notification to the source and/or destination of the data unit. Namely, as e.g. known from TCP (Transmission Control Protocol), congestion control mechanisms are typically implemented with respect to the receiver and sender of data units, such that when detecting that a data unit has been lost, the rate and/or amount of data units being sent is reduced.
Besides such queue managements systems that start dropping data units once a predetermined threshold is exceeded, i.e. when the queue is determined to be “full”, a more sophisticated management scheme has also been proposed, which is known as active queue management and is described in Request for Comments (RfC) 2309. More specifically RfC 2309 proposes an active queue management mechanism referred to as Random Early Detection (RED). The concept of RED according to RfC 2309 consists in the recognition that it is useful to not wait until a queue is full, but to much rather implement a mechanism that leads to a dropping of some packets prior to reaching the full state.
According to RfC2309, the RED algorithm consists of two main parts, namely first estimation of the average queue size and then a decision of whether or not to drop an incoming data unit. More specifically, when a new data unit arrives, the algorithm estimates the average queue size, and if the average queue size lies between a minimum threshold minth and a maximum threshold maxth, then a probability value is calculated as a function of the average queue size, and the decision regarding the dropping of the incoming data unit is performed in dependence of the resulting probability. If the average queue size exceeds the maximum threshold maxth, then the incoming data unit is necessarily dropped. The probability funtion is a linear function that has a value p(minth)=0, and where p(maxth) is a predetermined maximum probability maxp, where maxp is smaller than 1.
Regarding the choice of the minimum threshold minth or the maximum threshold maxth, RfC2309 does not give any information.
In the paper “Random Early Detection Gateways for Congestion Avoidance” by Sally Floyd and Van Jacobson, IEEE/ACM Transactions on networking, August 1993, an extensive discussion of the RED algorithm is given, where the minimum threshold minth, maximum threshold maxth and the maximum probability maxp are all set as fixed parameters. Regarding the choice of minth and maxth, it is mentioned that the optimum values for these thresholds depend on the desired average queue size, and the optimal value for maxth depends in part on the maximum average delay that can be allowed by the link. Furthermore, it is stated that maxth should at least be twice as large as minth.
In an internet document discussing the setting of RED parameters, published by Sally Floyd at http://www.acir.org/floyd/REDparameter.txt, it is mentioned that the optimum value for fixing minth will depend partly on the link speed, the propagation delay and the maximum buffer size.
In the article “Techniques for eliminating packet loss in congested TCP-IP networks” by Wu-chang Feng et al., November 1997, a so-called adaptive RED is proposed, in which the probability parameter maxp is adapted to the traffic load. Although the detailed algorithm described in this document uses fixed thresholds, it is indicated at the end that the threshold values could also be made dependent on the input traffic. A similar proposal is made in the article “A self configuring RED gateway” by Wu-chang Feng et al., Infocom '99, March 1999.
Another proposal for improving RED is made in WO 00/60817, in which a differentiation is introduced between traffic originating from rate adaptive applications that respond to packet loss. This document suggests introducing at least two drop precedent levels, referred to as “in profile” and “out profile”. Each drop precedent level has its own minimum threshold minth and/or maximum threshold maxth.
From WO 00/57599 a queue management mechanism is known, in which drop functions are selected according to ingress flow rate measurements and flow profiles.
From U.S. Pat. No. 6,134,239 a method of rejecting ATM cells at an overloaded load buffer is known. The concept of RED is mentioned. According to this document, a first threshold related to the overloaded buffer queue, and a second threshold associated with a specific connection are monitored, and incoming packets are dropped for the specific connection if both thresholds are exceeded.
U.S. Pat. No. 5,546,389 describes a method for controlling the access to a buffer and is specifically concerned with ATM buffers. The use of one or more thresholds and the dynamic control of such thresholds is mentioned, where the dynamics are determined on the basis of incoming and outgoing traffic.
EP-1 028 600 described a buffer management scheme with dynamic queue length thresholds for ATM switches. A common threshold is dynamically updated every time that a new cell arrives, where the new value is determined based on traffic condition.
Another improvement proposal for RED is described in EP-0 872 988, which has the object of providing isolation when connections using different TCP versions share a bottleneck link. The solution proposed in this document is the use of bandwidth reservation guarantees for each connection. If one connection is being under-utilized, then another connection may use a part of the under-utilized connection's bandwidth. When the connection needs to reclaim its buffer space a predetermined package dropping mechanism is operated, such as a longest queue first (LQF) mechanism.